/*
如果times = 0；选定一个为目标数
如果下一个数与目标数相同，那么times++
如果下一个数与目标数不同，那么times--
数组中出现次数最多的数最终会使得times > 0
 */
public class E39_2 {
    public static void main(String[] args) {
        int[] array = {1,2,3,2,2,2,5,4,2};
        int res = MoreThanHalfNum_Solution(array);
        System.out.println(res);
    }

    public static int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length <= 0){
            return 0;
        }

        int res = array[0];
        int times = 1;
        for(int i = 1; i < array.length; i++){
            if(0 == times){
                res = array[i];
                times = 1;
            }
            else if(array[i] == res){
                times ++;
            }
            else{
                times--;
            }
        }
        if(!CheckMoreThanHalf(array, res)){
            return 0;
        }
        return res;
    }

    public static boolean CheckMoreThanHalf(int[] array, int num){
        int count = 0;
        for(int a : array){
            if(a == num){
                count ++;
            }
        }
        return count >(array.length >> 1);
    }
}
